👤 Odin Hoff Gardå
✉️ odin.garda@uib.no
❗️Please try to solve the exercises yourself before looking at the solutions.❗️
Let f\colon X\to Y be a function. Then f is
There are many ways to do this. Don't worry if your solution is different from the proposed one.
General tips:
- Do you see a pattern or some property all elements in the set share?
- Can you describe this property using symbols?
For example, the set S=\{1,4,9,16,25,36\} consists of the squares 1^2, 2^2, 3^2, 4^2, 5^2, 6^2 so we can write S as follows using set builder notation:
S=\{n^2\mid n\in\mathbb{Z} \wedge (1\leq n\leq 6)\}
| Symbol | Meaning |
|---|---|
| \{ | Start of the definition of a set |
| n^2 | consider the elements n^2 |
| \mid | where |
| n\in\mathbb{Z} | n is an integer |
| \wedge | and |
| 1\leq n\leq 6 | n is 1,2,3,4,5 or 6 |
| \} | end of the definition of a set |
a) Here are three possible ways to do it:
b) \{n\in\mathbb{Z}\mid -3\leq n\leq 3\}
c) There is no clearly obvious way to do this. But let's try something:
Rememeber that every element in a set is unique. So for example, \{a,a,b,c\} = \{a,b,c\}. Sets cannot encode duplicates! (If you want to do this, you can look up the notion of multisets. But this is probably not a part of this course.)
Also, sets don't care about the order of elements. For example, \{a,b,c\} = \{b,a,c\}.
Note that the set containing a is not the same as a. That is, \{a\}\neq a.
a) Yes they are the same set.
b) They are not equal.
c) They are not equal. The set \emptyset contains no elements. However, the set \{\emptyset\} contains the element \emptyset.
For a set A to be a subset of another set B (written A\subseteq B, or A\subset B) it is sufficient and necessary that for all elements a in A, a is also in B. Symbolically, that is A\subseteq B \iff \forall a (a\in A\implies a\in B).
If the set A has strictly more elements than B, then there is no way A can be a subset of (or equal to) B. This restricts the number of inclusions you have to check.
For every set A, we have A\subseteq A but this is not interesting.
We only have to check the following inclusions:
Step 0: Try some examples:
| A | B | A\times B |
|---|---|---|
| \emptyset | \emptyset | \emptyset |
| \{a\} | \emptyset | \emptyset |
| \emptyset | \{b\} | \emptyset |
| \{a\} | \{b\} | \{(a,b)\} |
| \{a,c\} | \{b\} | \{(a,b), (c,b)\} |
| \{a,c\} | \{b,d\} | \{(a,b), (c,b), (a,d), (c,d)\} |
| \mathbb{R} | \mathbb{R} | \mathbb{R}^2 |
Step 1: Guess some hypothesis!
Step 2: Prove your hypothesis!
\begin{align*}
& A\times B =\{(a,b)\mid a\in A\wedge b\in B\} = \emptyset\\
&\iff \neg(\exists a\exists b (a\in A \wedge b\in B))\equiv \forall a\forall b (a\notin A \vee b\notin B)\\
&\iff A=\emptyset \vee B=\emptyset
\end{align*}
By the definition of ordered pairs given in the exercise, we have (a,b)=\{\{a\},\{a,b\}\} and (c,d)=\{\{c\},\{c,d\}\}. Let us write A=(a,b) and C=(c,d) to keep things simple. We need to show that A=C\iff (a=c\wedge b=d). We can split the proof into two parts. Namely,
The implication (2) is easy: if a=c and b=d, then A=\{\{a\},\{a,b\}\}=\{\{c\},\{c,d\}\}=C so we are done.
Now, try to give a convincing argument for (1). That is, argue why \{\{a\},\{a,b\}\}=\{\{c\},\{c,d\}\} implies that a=c and b=d. What does it mean for sets to be equal? And how can we check it?
Try to consider the two possible cases a=b and a\neq b. If a=b then \{\{a\},\{a,b\}\} = \{\{a\},\{a,a\}\} = \{\{a\},\{a\}\} = \{\{a\}\}.
a) A\cup B consists of all elements that are contained in A or B (or both).
b) A\cap B consists of all elements that are both in A and B.
c) and d) A\setminus B = A-B contains all elements of A that are not contained in B.
a) \{0,1,2,3,4,5,6\}
b) \{3\}
c) \{1,2,4,5\}
d) Similar to (c).
One way of proving this is to write both sides of the equality symbol using set builder notation and then (hopefully) realize that the two sides represents the same thing.
Recall the following definitions:
Another way is to show that the left-hand side is contained in the right-hand side, and the other way around.
You could also try to use a Venn diagram, or use some set identities you know.
b) (A\cap B)\cup(A\cap\bar{B}) = \{x\mid (x\in A\wedge x\in B)\vee (x\in A \wedge x\notin B) \} = \{x\mid (x\in A)\wedge(x\in B \vee x\notin B) \} = \{x\mid (x\in A)\wedge\textbf{T} \}=\{x\mid x\in A\} = A
a)
\begin{align*}
\bigcup_{i=1}^\infty A_i &= \bigcup_{i=1}^\infty\{i,i+1,i+2,\ldots,\} = \{1,2,3,4,\ldots\}\cup\{2,3,4,5\ldots\}\cup\ldots = \{1,2,3,4,5,6,\ldots\} = \{n\in\mathbb{Z}\mid n>0\}\\
\bigcap_{i=1}^\infty A_i &= \bigcap_{i=1}^\infty\{i,i+1,i+2,\ldots,\} = \{1,2,3,4,\ldots\}\cap\{2,3,4,5\ldots\}\cap\ldots = \emptyset
\end{align*}
The last one (intersection): if n\in\bigcap_{i=1}^\infty A_i then n\in A_i for all choices of i. Choose i=n+1, then n\in A_{n+1} = \{n+1, n+2, n+3,\ldots\} which is clearly not true. Hence, there are exists not n such that n\in\bigcap_{i=1}^\infty A_i which means it is the empty set.
b)
\begin{align*}
\bigcup_{i=1}^\infty A_i &= \bigcup_{i=1}^\infty\{0,i\} = \{0,1\}\cup\{0,2\}\cup\{0,3\}\cup\ldots = \{0,1,2,3,4,\ldots\}= \{n\in\mathbb{Z}\mid n\geq 0\}\\
\bigcap_{i=1}^\infty A_i &= \bigcap_{i=1}^\infty\{0,i\} = \{0,1\}\cap\{0,2\}\cap\{0,3\}\cap\ldots = \{0\}
\end{align*}
c)
\begin{align*}
\bigcup_{i=1}^\infty A_i &= \bigcup_{i=1}^\infty(0,i) = (0,1)\cup(0,2)\cup(0,3)\cup\ldots\cup(0,i)\cup\ldots = (0,\infty) = \{x\in \mathbb{R}\mid x>0\}\\
\bigcap_{i=1}^\infty A_i &= \bigcap_{i=1}^\infty(0,i) = (0,1)\cap(0,2)\cap(0,3)\cap\ldots\cap(0,i)\cap\ldots = (0,1)
\end{align*}
d)
\begin{align*}
\bigcup_{i=1}^\infty A_i &= \bigcup_{i=1}^\infty(i,\infty) = (1,\infty)\cup(2,\infty)\cup(3,\infty)\cup\ldots = (1,\infty) = \{x\in \mathbb{R}\mid x>1\}\\
\bigcap_{i=1}^\infty A_i &= \bigcap_{i=1}^\infty(i,\infty) = (1,\infty)\cap(2,\infty)\cap(3,\infty)\cap\ldots = \emptyset
\end{align*}
Explanation for the last one: Assume x is an element of \bigcap_{i=1}^\infty(i,\infty). Then, x\in(i,\infty) for all values of i by the definition of the intersection. But choose i to be some integer larger than x (for example, choose i=\lceil x \rceil+1) and we have x\notin (i,\infty) which is a contradiction. Therefore, our assumption must be wrong. That is, there are no elements in \bigcap_{i=1}^\infty(i,\infty) which means that it must be the empty set \emptyset.
a) What is the definition of a function? Can a function map an element to two elements?
b) Does it satisfy what it takes to be a function \mathbb{Z}\to\mathbb{R}?
c) Is it defined for all values in the domain \mathbb{Z}?
a) No, a function f\colon A\to B maps an element a\in A to exaclty one element f(a)\in B.
b) Yes this defines a function f\colon\mathbb{Z}\to\mathbb{R}.
c) No, the expression is undefined whenever n=2 or n=-2.
What is the definition of being one-to-one (injective)?
How can a function fail to be one-to-one?
Can a function that maps two or more elements to the same element be injective?
A bijection is a function that is both injective (one-to-one) and surjective (onto).
a) Yes (Check it!)
b) No (Same reason as (d). See below.)
c) Yes (Check it!)
d) No (It's always positive so it can't be surjective. Also, f(x)=f(-x) so it's not injective either.)
Set y=ax+b and solve for x. How does this give you the inverse of f?
Here is a graphical "proof" that a linear function (in one dimension) is invertible:
Writing y=ax+b and solving for x we get x=\frac{y-b}{a}. So I claim that g(y) = \frac{y-b}{a} is the inverse of f.
Let's check the claim:
Indeed we have that g=f^{-1}.